#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <vector>
#include <set>

/*
无相图的拓扑序：查找入度 <= 1的点，并删去和它相邻的边，重复，直到图中不存在点
*/
using namespace std;
using LL = long long;
using PII = pair<int, int>;
const int N = 4e5 + 10;

int n, k;
int cnt[N];
bool st[N];
vector<int> con[N];

void solve(){
    cin >> n >> k;

    int res = n;
    for(int i = 1; i <= n; i ++){
        st[i] = true;
        cnt[i] = 0;
        con[i].clear();
    }
    for(int i = 1, a, b; i < n; i ++){
        cin >> a >> b;
        cnt[a] ++;
        cnt[b] ++;
        con[a].push_back(b);
        con[b].push_back(a);
    }

    vector<int> t1;
    for(int i = 1; i <= n; i ++) {
        if(cnt[i] <= 1){
            t1.push_back(i);
            st[i] = false;
        }
    }

    while(k --){
        if(t1.empty()) break;

        vector<int> t2;
        for(int i = 0; i < t1.size(); i ++){
            int u = t1[i];
            res --;
            for(int j = 0; j < con[u].size(); j ++){
                cnt[con[u][j]] --;

                if(st[con[u][j]] && cnt[con[u][j]] <= 1){
                    t2.push_back(con[u][j]);
                    st[con[u][j]] = false;
                }
            }
        }

        t1 = t2;
    }


    cout << res << '\n';

    
    
}

int main(){
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);



    int T;
    cin >> T;
    while(T--){
        solve();
    }

    
    return 0;
}